Rudin–Shapiro sequence

In mathematics the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence is an infinite automatic sequence named after Marcel Golay, Walter Rudin and Harold S. Shapiro, who independently investigated its properties.[1]

Contents

Definition

Each term of the Rudin-Shapiro sequence is either +1 or −1. The nth term of the sequence, bn, is defined by the rules:

a_n=\textstyle\sum \varepsilon_i \varepsilon_{i%2B1}
b_n=(-1)^{a_n}

where the εi are the digits in the binary expansion of n. Thus an counts the number of (possibly overlapping) occurrences of the sub-string 11 in the binary expansion of n, and bn is +1 if an is even and −1 if an is odd.[2]

For example, a6 = 1 and b6 = −1 because the binary representation of 6 is 110, which contains one occurrence of 11; whereas a7 = 2 and b7 = +1 because the binary representation of 7 is 111, which contains two (overlapping) occurrences of 11.

Starting at n = 0, the first few terms of the an sequence are:

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (sequence A014081 in OEIS)

and the corresponding terms bn of the Rudin–Shapiro sequence are:

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, ... (sequence A020985 in OEIS)

Properties

The Rudin–Shapiro sequence can be generated by a four state automaton.[3]

The values of the terms an and bn in the Rudin–Shapiro sequence can be found recursively as follows. If n = m.2k where m is odd then

a_n = \begin{cases} a_{(m-1)/4} & \text{if } m = 1 \mod 4 \\ a_{(m-1)/2} %2B 1 & \text{if } m = 3 \mod 4 \end{cases}
b_n = \begin{cases} b_{(m-1)/4} & \text{if } m = 1 \mod 4 \\ -b_{(m-1)/2} & \text{if } m = 3 \mod 4 \end{cases}

Thus a108 = a13 + 1 = a3 + 1 = a1 + 2 = a0 + 2 = 2, which can be verified by observing that the binary representation of 108, which is 1101100, contains two sub-strings 11. And so b108 = (−1)2 = +1.

The Rudin-Shapiro word +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ..., which is created by concatenating the terms of the Rudin–Shapiro sequence, is a fixed point of the morphism or string substitution rules

+1 +1 → +1 +1 +1 −1
+1 −1 → +1 +1 −1 +1
−1 +1 → −1 −1 +1 −1
−1 −1 → −1 −1 −1 +1

as follows:

+1 +1 → +1 +1 +1 −1 → +1 +1 +1 −1 +1 +1 −1 +1 → +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ...

It can be seen from the morphism rules that the Rudin–Shapiro string contains at most four consecutive +1s and at most four consecutive −1s.

The sequence of partial sums of the Rudin–Shapiro sequence, defined by

s_n = \sum_{k=0}^n b_k \, ,

with values

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (sequence A020986 in OEIS)

can be shown to satisfy the inequality

\sqrt{\frac{3n}{5}} < s_n < \sqrt{6n} \text{ for } n \ge 1 \, .[1]

See also

Notes

  1. ^ a b A Case Study in Mathematical Research: The Golay–Rudin–Shapiro Sequence, John Brillhart and Patrick Morton
  2. ^ Weisstein, Eric W., "Rudin-Shapiro Sequence" from MathWorld.
  3. ^ Finite automata and arithmetic, Jean-Paul Allouche

References